package leetcode.offer;

import leetcode.common.TreeNode;

@SuppressWarnings("all")
public class 二叉树中距离最远的两个结点的距离 {

    private int maxLen = 0;

    // 该方法返回从root节点出发，向左或向右所能走的最远距离
    //（该方法的返回值并非是整个树的最远距离，而是它的左子树最远距离和右子树最远距离两者中的较大值）
    // maxLen用于保存整个二叉树的最远距离
    public int findMaxLen(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 0;
        }
        // 当前结点往左走的最大距离
        int leftMaxLen = findMaxLen(root.left) + 1;
        // 当前结点往右走的最大距离
        int rightMaxLen = findMaxLen(root.right) + 1;
        // 左右最大距离加当前结点=当前根节点出发左右子结点的最远距离
        int maxTemp = leftMaxLen + rightMaxLen + 1;
        if (maxTemp > maxLen) {
            maxLen = maxTemp;
        }
        // 该函数的本质是在求以当前结点为出发点的最大深度
        // 只是在求最大深度的同时求出二叉树中两结点的最远距离
        return Math.max(leftMaxLen, rightMaxLen);
    }

    // 测试
    public static void main(String[] args) {
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node10 = new TreeNode(10);
        TreeNode node11 = new TreeNode(11);
        TreeNode node9 = new TreeNode(9);
        TreeNode node12 = new TreeNode(12);
        TreeNode node13 = new TreeNode(13);

        node2.left = node3;
        node2.right = node4;
        node3.left = node5;
        node3.right = node6;
        node5.left = node7;
        node7.left = node10;
        node10.left = node11;
        node6.right = node9;
        node9.right = node12;
        node12.left = node13;

        二叉树中距离最远的两个结点的距离 test = new 二叉树中距离最远的两个结点的距离();
        // 从node2节点出发，向左走能走5，向右走能走1，因此返回二者中较大的值5
        int out = test.findMaxLen(node2);
        System.out.println(out);
        // maxLen返回的才是二叉树的最远距离
        System.out.println(test.maxLen);
    }
}
